Arrays¶
- Why are arrays so popular?
Arrays¶
Why are arrays so popular?
- Given any index $i$, we can access $A[i]$ quickly (in constant time)
How do you think they are typically implemented?
Arrays¶
Given any index $i$, we can access $A[i]$ quickly (in constant time)
Usually implemented as contiguous locations in memory
Time complexities of the operations?¶
insert at index
delete
search
insert at the beginning
insert at the end
static: size does not change at runtime
dynamic: size may change at runtime
Linked Lists¶
class ListNode :
def __init__(self, data) :
self.data = data
self.next = None
Linked List¶
- A singly linked list
- Each node contains a single link field
- allows for a complete traversal from a distinctive first node to the last.
- a = ListNode(11)
- b = ListNode(52)
- c = ListNode(18)
Please pay attention to how the boxes and arrows are drawn!¶
a = ListNode(11)
b = ListNode(52)
c = ListNode(20)
print(a.data)
print(b.data)
print(c.data)
11 52 20
a.next = b
b.next = c
- a.next = b
- b.next = c
# Print elements in the list
# print(a)
# while a != None:
# print (a.data, end=" ")
# a = a.next
tmp = a
while tmp != None:
print (tmp.data, end=" ")
tmp = tmp.next
11 52 20
#print(a.data)#11
#print(a.next.data)#18
#print(a.next.next.data)#318
head = a
#print(head.next.next.next.data)
tmp = head
lookingfor = 18
if (tmp != None):
if tmp.data == lookingfor:
print(tmp.data)
else:
while(tmp.next != None) and (tmp.next.data != lookingfor):
tmp = tmp.next
if tmp.next != None:
print(tmp.next.data)
else:
print("not found")
else:
print("list empty")
# next, do the actual insert
not found
# Search through the elements
head = a # the head points to the first elem in the list
lookingfor = 20
flgfound = False
curr = head # begin at the beginning
while curr != None:
if (curr.data == lookingfor): # check for the content (data)
print("found what you are looking for! :-)")
flgfound = True
break
curr = curr.next # move to the next node
if (flgfound == False):
print("could not find it :-(")
found what you are looking for! :-)
# Search through the elements without the flag
head = a # the head points to the first elem in the list
lookingfor = 20
curr = head # begin at the beginning
while curr != None:
if (curr.data == lookingfor): # check for the content (data)
print("found what you are looking for! :-)")
break
curr = curr.next # move to the next node
if (curr == None):
print("could not find it :-(")
found what you are looking for! :-)
class ComplicatedNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
self.third = None
self.fourth = None
ca = ComplicatedNode(10)
cb = ComplicatedNode(20)
cc = ComplicatedNode(30)
ca.left = cb
ca.right = cc
print(ca.left.data)
print(ca.right.data)
Find 18
Copy 18's next to 96's next
- 96's next will point to 36
Point 18's next to 96
- 18's next will point to 96
We are done!
What happens if we do 3 before 2 above?¶
Point 18's next to 96
- 18's next will point to 96
Point 18's next to 96's next
Remove a node from a list¶
Remove a node from a list¶
It makes matters easier to have a predecessor¶
head = a # head always points to the first element of the list
rmval = 18
curr = head
prev = None
while curr != None:
if curr.data == rmval:
if prev == None: # first guy in the list
head = head.next
else:
prev.next = curr.next
break
prev = curr
curr = curr.next
tmp = head
while tmp != None:
print(tmp.data,end=" ")
tmp = tmp.next
print("")
Time complexities of the operations?¶
insert
delete
search
insert at the beginning
insert at the end
Append to the end of a list¶
The same algorithm that works for insert will work for append ("insert at the end")
Suppose this operation needs to happen frequently.
Append to the end of a list¶
This is happening often, taking $O(n)$ time, each time...
Any ideas?
Let's use a tail !¶
What are the advantages of using a tail?¶
Just one extra variable
Independent of $n$ - the length of the list
Makes append a constant time operation!!
Doubly-linked Lists¶
class DListNode :
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
a = DListNode(21)
b = DListNode(57)
c = DListNode(38)
d = DListNode(14)
a.next = b
b.prev = a
b.next = c
c.prev = b
c.next = d
d.prev = c
head = a
tail = d
curr = head
print("forward:")
while curr != None:
print(curr.data,end=" ")
curr = curr.next
print("\nbackward:")
curr = tail
while curr != None:
print(curr.data,end=" ")
curr = curr.prev
forward: 21 57 38 14 backward: 14 38 57 21
Add a node to a doubly linked list¶
def dllprintf(dll):
curr = head
while curr != None:
print(curr.data,end =" ")
curr = curr.next
print("")
def dllprintb(dll):
curr = tail
while curr != None:
print(curr.data,end =" ")
curr = curr.prev
print("")
# The current list contains
dllprintf(head)
# Add it between the second and third nodes
second = head.next
third = second.next
newnode = DListNode(46)
print("\nadding the newnode between the 2nd and 3rd elements")
newnode.next = third
newnode.prev = second
second.next = newnode
third.prev = newnode
dllprintf(head)
dllprintb(tail)
21 57 38 14 adding the newnode between the 2nd and 3rd elements 21 57 46 38 14 14 38 46 57 21
Homework :-P¶
Add a node at the beginning of a doubly linked list
Add a node at the end of a doubly linked list
Circular Linked Lists¶
- Used in operating systems to serve jobs in round-robin fashion (CPU scheduling)
Matrices ("may-tree-ceez")¶
- singular matrix pronounced "may-tricks"
- pronounciation often confused with metrics "me(short)-tricks"
2D Arrays¶
# Implementation of the Array2D ADT using an array of arrays.
class Array2D : # Creates a 2-D array of size numRows x numCols.
def __init__( self, numRows, numCols ):
# Create a 1-D array to store an array reference for each row.
self._Rows = [0]*( numRows )
# Create the 1-D arrays for each row of the 2-D array.
for i in range( numRows ) :
self._Rows[i] = [i]*( numCols )
# Returns the number of rows in the 2D array
def numRows( self ):
return len( self._Rows )
# Returns the number of columns in the 2D array
def numCols( self ):
return len( self._Rows[0] )
# Prints the entire array
def prn2d( self ):
for i in range( len(self._Rows )):
for j in range( len(self._Rows[0]) ):
print(self._Rows[i][j],end=" ")
print("")
return("")
def setrow( self, rowNum, contents ):
for j in range( len(self._Rows[0])):
self._Rows[rowNum][j] = contents[j]
a2 = Array2D(4, 6)
print("No. of rows: ",a2.numRows())
print("No. of cols: ",a2.numCols())
print(a2.prn2d())
No. of rows: 4 No. of cols: 6 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3
mycon0 = [".",".","-","-",".","."]
mycon1 = [".",".","0","0",".","."]
mycon2 = [".",".","^","^",".","."]
mycon3 = [".","\\","-","-","/","."]
a2.setrow(0,mycon0)
a2.setrow(1,mycon1)
a2.setrow(2,mycon2)
a2.setrow(3,mycon3)
print(a2.prn2d())
. . - - . . . . 0 0 . . . . ^ ^ . . . \ - - / .
The Game of Life¶
Birth rule: An empty, or “dead,” cell with precisely three “live” neighbours (full cells) becomes live.
Death rule: A live cell with zero or one neighbours dies of isolation; a live cell with four or more neighbours dies of overcrowding.
Survival rule: A live cell with two or three neighbours remains alive
(https://www.nytimes.com/2020/12/28/science/math-conway-game-of-life.html)
Birth rule: An empty, or “dead,” cell with precisely three “live” neighbours (full cells) becomes live.
Death rule: A live cell with zero or one neighbours dies of isolation; a live cell with four or more neighbours dies of overcrowding.
Survival rule: A live cell with two or three neighbours remains alive
(https://www.nytimes.com/2020/12/28/science/math-conway-game-of-life.html)
The Game of Life¶
Complex patterns from simple rules
An example of a "cellular automaton"
Formal model of a computer
Implement Matrix Operations using 2D Arrays¶
Add a matrix to this one.
Subtract a matrix from this one.
Multiply a matrix with this one.
Transpose this matrix
Matrix Addition and Subtraction¶
Matrix Scaling¶
Matrix Multiplication¶
Matrix Transpose¶
# Implementation of the Array2D ADT using an array of arrays.
class Array2D : # Creates a 2-D array of size numRows x numCols.
def __init__( self, numRows, numCols ):
# Create a 1-D array to store an array reference for each row.
self._Rows = [0]*( numRows )
# Create the 1-D arrays for each row of the 2-D array.
for i in range( numRows ) :
self._Rows[i] = [i]*( numCols )
# Returns the number of rows in the 2D array
def numRows( self ):
return len( self._Rows )
# Returns the number of columns in the 2D array
def numCols( self ):
return len( self._Rows[0] )
# Prints the entire array
def prn2d( self ):
for i in range( len(self._Rows )):
for j in range( len(self._Rows[0]) ):
print(self._Rows[i][j],end=" ")
print("")
#return()
def setrow( self, rowNum, contents ):
for j in range( len(self._Rows[0])):
self._Rows[rowNum][j] = contents[j]
mya = Array2D(2,4)
mya.prn2d()
Implementation of Matrix operations¶
- In Python and Java, you can define classes
- The "matrix" class can use the "Array2D" class
Each one of the matrix operations: add, subtract, multiply etc. will become methods
A "function" defined inside a class is called a "method"
An "object" (variable) M1 of "class" (type) Array2D can "invoke" (call) a "method" (function) "prn2D" using the "." operator.
mya = Array2D(2,4)
mya.prn2d( )
- The "matrix" class can use the "Array2D" class
# Implementation of the Matrix ADT using a 2-D array.¶
from array import Array2D
class Matrix :
# Creates a matrix of size numRows x numCols initialized to 0.
def __init__( self, numRows, numCols ):
self._theGrid = Array2D ( numRows, numCols )
Implementation of the Matrix ADT using a 2-D array.¶
Example of inheritance¶
class Matrix (Array2D):
# Creates a matrix of size numRows x numCols initialized to 0.
def __init__( self, numRows, numCols ):
Array2D.__init__(self, numRows, numCols)
# Returns the number of rows in the 2D array
def numRows( self ):
return super().numRows()
# Returns the number of columns in the 2D array
def numCols( self ):
return Array2D.numCols()
# Prints the entire array
def prn2d( self ):
return super().prn2d( )# Implementation of the Matrix ADT using a 2-D array.
# Example of inheritance
class Matrix (Array2D):
# Creates a matrix of size numRows x numCols initialized to 0.
def __init__( self, numRows, numCols ):
Array2D.__init__(self, numRows, numCols)
# Returns the number of rows in the 2D array
def numRows( self ):
return super().numRows()
# Returns the number of columns in the 2D array
def numCols( self ):
return Array2D.numCols()
# Prints the entire array
def prn2d( self ):
return super().prn2d( )
M = Matrix(3,5)
M.numRows()
M.prn2d()
0 0 0 0 0 1 1 1 1 1 2 2 2 2 2
Sparse Matrix¶
A matrix containing a large number of zeros
Where?
- Very common in scientific applications, as in systems of linear equations.
- Very common in scientific applications, as in systems of linear equations.
Sparse Matrix¶
Where else?
Suppose I build a graph of "who-knows-whom" in Ahmedabad University
folks-in-DS | rest-of-the-folks -------------------|----------------------------------------------- 1 1 1 1 0 1 1 1 0 | 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 | 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0
The story so far...¶
Recursion
- Mathematical
- Programming
- Problems with both types of solutions: recursive and iterative
- Efficiency
Algorithm Analysis
- "count steps" instead of timing programs (time-complexity)
- "rough upper bound" of time-complexity $\longrightarrow$ big-Oh notation
- $O(n), O(\log n), O(n^2)...$
The story so far...¶
- Linear Data Structures
- Arrays
- Linked Lists
- Time complexity of basic operations
- Comparisons